package com.copa.l22;

import java.util.ArrayList;
import java.util.List;

/**
 * @author copa
 * @createDate 2022-04-28 16:47
 * @function 回溯法，具体解法看title.txt
 */
public class Test1 {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        generate(n, result, 0, 0, "");
        return result;
    }

    /**
     *
     * @param n       用户输入匹配个数
     * @param result  输出结果
     * @param left    左括号个数
     * @param right   右括号个数
     * @param str     当前字符串
     */
    private void generate(int n, List<String> result, int left, int right, String str) {
        if (right > left) {
            // 如果右括号个数大于左括号个数，不合法，应当回溯
            return;
        }
        if (left == right && left == n) {
            // 如果右括号个数等于左括号个数且等于用户输入个数，说明是合法的str，应当加入到结果当中，回溯继续
            result.add(str);
            return;
        }
        if (n > left) {
            // 如果用户输入个数大于左括号个数，说明此时需要添加左括号进行递归
            generate(n, result, left + 1, right, str + "(");
        }
        if (left > right) {
            // 如果左括号个数大于右括号个数，说明此时需要添加右括号进行递归
            generate(n, result, left, right + 1, str + ")");
        }
    }

    public static void main(String[] args) {
        List<String> generateParenthesis = new Test1().generateParenthesis(2);
        for (String parenthesis : generateParenthesis) {
            System.out.println(parenthesis);
        }
    }
}
